package com.lga.algorithm;

import java.util.Arrays;

public class Sort {

    /**
     * 插入排序
     *
     * @param a 需要排序的数组
     * @param n 数组的大小
     */
    public static void insertSort(int[] a, int n) {
        for (int i = 1; i < n; i++) {
            int value = a[i];
            int j = i - 1;
            //查找插入的位置
            for (; j >= 0; j--) {
                if (a[j] > value) {
                    a[j + 1] = a[j]; //数据移动
                } else {
                    break;
                }
            }
            a[j + 1] = value;
        }
    }

    /**
     * 快速排序
     *
     * @param a
     * @param n
     */
    public static void quickSort(int[] a, int n) {
        quick_sort(a, 0, n - 1);
    }

    private static void quick_sort(int[] a, int p, int r) {
        if (p >= r) {
            return;
        }

        int q = partition(a, p, r); //得到分区点的坐标
        quick_sort(a, p, q - 1);
        quick_sort(a, q + 1, r);
    }

    private static int partition(int[] a, int p, int r) {
        int i = p;
        int pivot = a[r];
        for (int j = p; j < r - 1; j++) {
            if (pivot > a[j]) {
                //交换a[i] 和 a[j]
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
            }
        }
        //交换a[i] 和 a[r]
        int temp = a[i];
        a[i] = a[r];
        a[r] = temp;
        return i;
    }

    public static void main(String[] args) {
        int[] a = new int[]{3, 5, 6, 4, 7, 2, 11, 8};
        quickSort(a, 8);
//        Sort.insertSort(a, a.length);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

}
